package leetcode;

/**
 * Created by Ghost on 2014/12/28 0028.
 */
public class Best_Time_to_Buy_and_Sell_Stock_III {
    private int getMaxProfit(int start,int end,int[] prices){
        int[] p = new int[end-start+1];
        p[0] = 0;
        int max = 0;
        for(int i=1;i<p.length;i++){
            p[i] = prices[i+start]-prices[i+start-1]+p[i-1]>=0?prices[i+start]-prices[i+start-1]+p[i-1]:0;
            max = max<p[i]?p[i]:max;
        }
        return max;
    }
    public int maxProfit(int[] prices) {
        if(prices.length==0)
            return 0;
        int max = getMaxProfit(0,prices.length-1,prices);
        for(int i=1;i<prices.length-1;i++){
            int aMax = getMaxProfit(0,i,prices);
            int bMax = getMaxProfit(i+1,prices.length-1,prices);
            max = max<aMax+bMax?aMax+bMax:max;
        }
        return max;
    }

    public static void main(String[] args){
        Best_Time_to_Buy_and_Sell_Stock_III best_time_to_buy_and_sell_stock_iii = new Best_Time_to_Buy_and_Sell_Stock_III();
        int[] num = {1};
        System.out.println(best_time_to_buy_and_sell_stock_iii.maxProfit(num));
    }
}
